#include <vector>
#include <string>
#include <algorithm>
#include <iostream>

using namespace std;

class Code07_UniqueSubstringsWraparoundString
{
public:
    // 时间复杂度O(n)，n是字符串s的长度，字符串base长度为正无穷
    static int findSubstringInWraproundString(string str)
    {
        int n = str.length();
        vector<int> s(n);

        // abcde...z -> 0, 1, 2, 3, 4....25
        for (int i = 0; i < n; i++)
        {
            s[i] = str[i] - 'a';
        }

        // dp[0] : s中必须以'a'的子串，最大延伸长度是多少，延伸一定要跟据base串的规则
        vector<int> dp(26, 0);

        // s : c d e....
        //     2 3 4
        dp[s[0]] = 1;
        for (int i = 1, cur, pre, len = 1; i < n; i++)
        {
            cur = s[i];
            pre = s[i - 1];
            // pre cur
            if ((pre == 25 && cur == 0) || pre + 1 == cur)
            {
                // (前一个字符是'z' && 当前字符是'a') || 前一个字符比当前字符的ascii码少1
                len++;
            }
            else
            {
                len = 1;
            }
            dp[cur] = max(dp[cur], len);
        }

        int ans = 0;
        for (int i = 0; i < 26; i++)
        {
            ans += dp[i];
        }
        return ans;
    }
};
int main()
{
    string str = "azbz";
    int result = Code07_UniqueSubstringsWraparoundString::findSubstringInWraproundString(str);

    // 输出结果
    cout << "The number of unique substrings in wraparound string is: " << result << endl;

    return 0;
}
